{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #玩具套圈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #hash-table #math #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #哈希表 #数学 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: circleGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #玩具套圈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "「力扣挑战赛」场地外，小力组织了一个套玩具的游戏。所有的玩具摆在平地上，`toys[i]` 以 `[xi,yi,ri]` 的形式记录了第 `i` 个玩具的坐标 `(xi,yi)` 和半径 `ri`。小扣试玩了一下，他扔了若干个半径均为 `r` 的圈，`circles[j]` 记录了第 `j` 个圈的坐标 `(xj,yj)`。套圈的规则如下：\n",
    "- 若一个玩具被某个圈完整覆盖了（即玩具的任意部分均在圈内或者圈上），则该玩具被套中。\n",
    "- 若一个玩具被多个圈同时套中，最终仅计算为套中一个玩具\n",
    "\n",
    "请帮助小扣计算，他成功套中了多少玩具。\n",
    "\n",
    "**注意：**\n",
    "- 输入数据保证任意两个玩具的圆心不会重合，但玩具之间可能存在重叠。\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    "\n",
    "> 输入：`toys = [[3,3,1],[3,2,1]], circles = [[4,3]], r = 2`\n",
    ">\n",
    "> 输出：`1`\n",
    "> \n",
    "> 解释： 如图所示，仅套中一个玩具\n",
    "![image.png](https://pic.leetcode-cn.com/1629194140-ydKiGF-image.png)\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    "\n",
    "> 输入：`toys = [[1,3,2],[4,3,1],[7,1,2]], circles = [[1,0],[3,3]], r = 4`\n",
    ">\n",
    "> 输出：`2`\n",
    "> \n",
    "> 解释： 如图所示，套中两个玩具\n",
    "![image.png](https://pic.leetcode-cn.com/1629194157-RiOAuy-image.png){:width=\"400px\"}\n",
    "\n",
    "\n",
    "\n",
    "**提示：** \n",
    "- `1 <= toys.length <= 10^4`\n",
    "- `0 <= toys[i][0], toys[i][1] <= 10^9`\n",
    "- `1 <= circles.length <= 10^4`\n",
    "- `0 <= circles[i][0], circles[i][1] <= 10^9`\n",
    "- `1 <= toys[i][2], r <= 10`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [vFjcfV](https://leetcode.cn/problems/vFjcfV/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [vFjcfV](https://leetcode.cn/problems/vFjcfV/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3,2],[4,3,1]]\\n[[1,0],[3,3],[0,0],[3,4]]\\n4', '[[3,4,5],[1,4,4],[4,4,1],[1,5,5]]\\n[[4,1],[4,2]]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        mp,ans={},0\n",
    "        for i in circles:mp[(i[0],i[1])]=1\n",
    "        for i in toys:\n",
    "            if(r<i[2]):continue\n",
    "            if(r==i[2]):ans+=mp.get((i[0],i[1]),0);continue\n",
    "            opt=0\n",
    "            for j in range(i[0]+i[2]-r,i[0]-i[2]+r+1):\n",
    "                for k in range(i[1]+i[2]-r,i[1]-i[2]+r+1):\n",
    "                    if(mp.get((j,k),0)):\n",
    "                        if((j-i[0])*(j-i[0])+(k-i[1])*(k-i[1])<=(r-i[2])*(r-i[2])):ans+=1;opt=1;break\n",
    "                if(opt):break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        result = 0\n",
    "        circles_dict = set()\n",
    "        for i in range(len(circles)):\n",
    "            circles_dict.add((circles[i][0],circles[i][1]))\n",
    "        for toy in toys:\n",
    "            left = r - toy[2]\n",
    "            mark = 0\n",
    "            if left<0:\n",
    "                continue\n",
    "            for i in range(-left,left+1):\n",
    "                for j in range(-left,left+1):\n",
    "                    if i*i+j*j<=left*left and (toy[0]+i,toy[1]+j) in circles_dict:\n",
    "                        mark =1\n",
    "                        break\n",
    "                if mark==1:\n",
    "                    break\n",
    "            if mark==1:\n",
    "                result +=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        result = 0\n",
    "        circles_dict = set()\n",
    "        for i in range(len(circles)):\n",
    "            circles_dict.add((circles[i][0],circles[i][1]))\n",
    "        for toy in toys:\n",
    "            left = r - toy[2]\n",
    "            mark = 0\n",
    "            for i in range(-left,left+1):\n",
    "                for j in range(-left,left+1):\n",
    "                    if i*i+j*j<=left*left and (toy[0]+i,toy[1]+j) in circles_dict:\n",
    "                        mark =1\n",
    "            if mark==1:\n",
    "                result +=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "\n",
    "        cirs = set()\n",
    "        for x,y in circles: #所有套圈的圆心进哈希集合\n",
    "            cirs.add((x,y))\n",
    "\n",
    "        def check(tx,ty,dif):\n",
    "            for cx in range(tx-dif,tx+dif+1):\n",
    "                for cy in range(ty-dif,ty+dif+1):\n",
    "                    #注意由于圆形区难以枚举，实际枚举的是该圆形区外切的正方形区，要判断一下是否真的是圆心距小于半径差\n",
    "                    if (cx-tx)*(cx-tx)+(cy-ty)*(cy-ty)<=dif*dif and (cx,cy) in cirs:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        ans = 0\n",
    "        for tx,ty,tr in toys:\n",
    "            ans+=check(tx,ty,r-tr) #如果套圈比玩具小，check函数根本不会循环，直接就False了，无需特判\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        circlesSet = set()\n",
    "        for x,y in circles:\n",
    "            circlesSet.add((x,y))\n",
    "        def check(x1, y1, r1):\n",
    "            d = r - r1\n",
    "            for x in range(max(0,x1-d),x1+d+1):\n",
    "                for y in range(max(0,y1-d),y1+d+1):\n",
    "                    if((x-x1)**2+(y-y1)**2<=d**2 and (x,y) in circlesSet):\n",
    "                        return True\n",
    "            return False\n",
    "        result = 0\n",
    "        for x1, y1, r1 in toys:\n",
    "            if(r1 > r):\n",
    "                continue\n",
    "            if(check(x1,y1,r1)):\n",
    "                result += 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        mp,ans={},0\n",
    "        for i in circles:mp[(i[0],i[1])]=1\n",
    "        for i in toys:\n",
    "            if(r<i[2]):continue\n",
    "            if(r==i[2]):ans+=mp.get((i[0],i[1]),0);continue\n",
    "            opt=0\n",
    "            for j in range(i[0]+i[2]-r,i[0]-i[2]+r+1):\n",
    "                p=int(sqrt((r-i[2])*(r-i[2])-(j-i[0])*(j-i[0])))\n",
    "                for k in range(i[1]-p,i[1]+p+1):\n",
    "                    if(mp.get((j,k),0)):ans+=1;opt=1;break\n",
    "                if(opt):break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        #print(int(-3.5))\n",
    "        #return \n",
    "        had = set()\n",
    "        for x, y in circles:\n",
    "            had.add((x, y))\n",
    "\n",
    "        cnt = 0\n",
    "        for x0, y0, r0 in toys:\n",
    "            if r0 > r:\n",
    "                continue\n",
    "            dif = r - r0  \n",
    "            find = False  \n",
    "            for x1 in range(x0 - dif, x0 + dif+1):\n",
    "                if find:\n",
    "                    break\n",
    "                \n",
    "                for y1 in range(y0- dif, y0+dif+1):\n",
    "                    if (x1, y1) in had and (y1 - y0)**2 + (x1-x0)**2 <= dif**2:\n",
    "                        cnt += 1\n",
    "                        find = True\n",
    "                        break\n",
    "\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        ans = 0\n",
    "        s = {(x, y) for x, y in circles}\n",
    "        for x, y, rr in toys:\n",
    "            d = r - rr\n",
    "            if d < 0:\n",
    "                continue\n",
    "            flag = False\n",
    "            for dx in range(-d, d + 1):\n",
    "                if flag:\n",
    "                    break\n",
    "                for dy in range(-d, d + 1):\n",
    "                    if dx * dx + dy * dy > d * d:\n",
    "                        continue\n",
    "                    if (x + dx, y + dy) in s:\n",
    "                        ans += 1\n",
    "                        flag = True\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "\n",
    "        cirs = set()\n",
    "        for x,y in circles: #所有套圈的圆心进哈希集合\n",
    "            cirs.add((x,y))\n",
    "\n",
    "        def check(tx,ty,dif):\n",
    "            for cx in range(tx-dif,tx+dif+1):\n",
    "                for cy in range(ty-dif,ty+dif+1):\n",
    "                    #注意由于圆形区难以枚举，实际枚举的是该圆形区外切的正方形区，要判断一下是否真的是圆心距小于半径差\n",
    "                    if (cx-tx)*(cx-tx)+(cy-ty)*(cy-ty)<=dif*dif and (cx,cy) in cirs:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        ans = 0\n",
    "        for tx,ty,tr in toys:\n",
    "            ans+=check(tx,ty,r-tr) #如果套圈比玩具小，check函数根本不会循环，直接就False了，无需特判\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        result = 0\n",
    "        circles_dict = set()\n",
    "        for i in range(len(circles)):\n",
    "            circles_dict.add((circles[i][0],circles[i][1]))\n",
    "        for toy in toys:\n",
    "            left = r - toy[2]\n",
    "            mark = 0\n",
    "            for i in range(-left,left+1):\n",
    "                for j in range(-left,left+1):\n",
    "                    if i*i+j*j<=left*left and (toy[0]+i,toy[1]+j) in circles_dict:\n",
    "                        mark =1\n",
    "                        break\n",
    "                if mark==1:\n",
    "                    break\n",
    "            if mark==1:\n",
    "                result +=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "\n",
    "        cirs = set()\n",
    "        for x,y in circles: #所有套圈的圆心进哈希集合\n",
    "            cirs.add((x,y))\n",
    "\n",
    "        def check(tx,ty,dif):\n",
    "            for cx in range(tx-dif,tx+dif+1):\n",
    "                for cy in range(ty-dif,ty+dif+1):\n",
    "                    #注意由于圆形区难以枚举，实际枚举的是该圆形区外切的正方形区，要判断一下是否真的是圆心距小于半径差\n",
    "                    if (cx-tx)*(cx-tx)+(cy-ty)*(cy-ty)<=dif*dif and (cx,cy) in cirs:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        ans = 0\n",
    "        for tx,ty,tr in toys:\n",
    "            ans+=check(tx,ty,r-tr) #如果套圈比玩具小，check函数根本不会循环，直接就False了，无需特判\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        result = 0\n",
    "        circles_dict = set()\n",
    "        for i in range(len(circles)):\n",
    "            circles_dict.add((circles[i][0],circles[i][1]))\n",
    "        for toy in toys:\n",
    "            left = r - toy[2]\n",
    "            mark = 0\n",
    "            for i in range(-left,left+1):\n",
    "                for j in range(-left,left+1):\n",
    "                    if i*i+j*j<=left*left and (toy[0]+i,toy[1]+j) in circles_dict:\n",
    "                        mark =1\n",
    "                        break\n",
    "                if mark==1:\n",
    "                    break\n",
    "            if mark==1:\n",
    "                result +=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:\n",
    "        # d[i] = 圆心距离<=i时，俩圆心的所有可能整数偏移量(dx, dy)\n",
    "        d = defaultdict(set)\n",
    "        for i in range(r+1):\n",
    "            d[i].add((0, 0))\n",
    "            for j in range(i+1):\n",
    "                for k in range(i+1):\n",
    "                    if j * j + k * k <= i * i:\n",
    "                        d[i].add((j, k)); d[i].add((-j, k)); d[i].add((j, -k)); d[i].add((-j, -k))\n",
    "\n",
    "        circles = set((x, y) for x, y in circles)\n",
    "        ans = 0\n",
    "        for x, y, rt in toys:\n",
    "            # 如果一个圈套中了当前玩具，则 圆心距离 <= r - rt\n",
    "            ans += any((x+dx, y+dy) in circles for dx, dy in d[r-rt])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
